#include <iostream>
#include <vector>
using namespace std;
/*
有 k 种颜色的涂料和一个包含 n 个栅栏柱的栅栏，请你按下述规则为栅栏设计涂色方案：

每个栅栏柱可以用其中 一种 颜色进行上色。
相邻的栅栏柱 最多连续两个 颜色相同。
给你两个整数 k 和 n ，返回所有有效的涂色 方案数 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/paint-fence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

int numWays(int n, int k)
{
    if (n == 0)
        return 0;
    else if (n == 1)
        return k;
    else if (n == 2)
        return k * k;
    vector<int> dp(n + 1);
    dp[1] = k;
    dp[2] = k * k;
    for (int i = 3; i <= n; i++)
    {
        dp[i] = dp[i - 1] * (k - 1) + dp[i - 2] * (k - 1); //即去掉本颜色，剩下k-1
    }
    return dp[n];
}